package JZ.JZ27;

/**
 * @author corn
 * @create 2020-08-08-20:46
 */

import java.util.ArrayList;
import java.util.TreeSet;

/**
 * JZ27 字符串的排列
 * 题目描述
 * 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,
 * 则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
 */
public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> result = new ArrayList<String>();
        //判空
        if(str==null || str.length()==0) {
            return result;
        }
        //将字符串转换成数组
        char[] chars = str.toCharArray();
        //用于对所有排列进行排序
        TreeSet<String> temp = new TreeSet<>();
        Permutation(chars,0,temp);
        result.addAll(temp);
        return result;
    }
    public void Permutation(char[] chars, int begin, TreeSet<String> result) {
        if(chars==null || chars.length==0 || begin<0 || begin>chars.length-1){
            return;
        }
        if(begin == chars.length-1) {
            //将数组转换成字符串添加到TreeSet中
            result.add(String.valueOf(chars));
        }else {
            for(int i=begin; i<=chars.length-1; i++) {
                //将begin位置的值与其后面的所有数字进行交换。
                swap(chars, begin, i);
                //进行后续点的交换
                Permutation(chars, begin+1, result);
                //将交换的点还原回去
                swap(chars, begin, i);
            }
        }
    }
    public void swap(char[] x, int a, int b) {
        char t = x[a];
        x[a] = x[b];
        x[b] = t;
    }
}
